package com.example.arithmeticleetcode.learnArithmetic2.sort;

/**
 * @program: arithmetic-leetcode
 * @description: 最好 平均时间复杂度O(nlogN) 最坏空间复杂度为O(n^2) 空间复杂度O(logN) 不稳定排序
 * @author: FangZhen
 * @create: 2020-11-10 12:16
 **/
public class QuickSort<E extends Comparable<E>> extends Sort<E> {

    @Override
    protected void sort() {
        sort(0, array.length);
    }

    /**
     * 对[begin, end) 范围的元素进行快速排序
     *
     * @param begin
     * @param end
     */
    private void sort(int begin, int end) {
        if (end - begin < 2) return;

        //确定轴点位置 O(n)
        int mid = pivotIndex(begin, end);
        //对子序列进行快速排序
        sort(begin, mid);//T(n/2)
        sort(mid + 1, end);//T(n/2)
    }

    /**
     * 构造出[begin, end)范围的轴点元素
     * @param begin
     * @param end
     * @return 轴点元素的最终位置
     */
    private int pivotIndex(int begin, int end) {
        //随机选择一个元素与begin位置进行交换
        swap(begin, begin + (int) Math.random()*(end - begin));
        //备份begin位置的元素
        E pivot = array[begin];
        //end指向最后一个元素
        end--;

        while (begin < end) {
            while (begin < end) {
                if (cmp(pivot, array[end]) < 0) { //右边元素>轴点元素
                    end--;
                } else { // 右边元素<=轴点元素
                    array[begin++] = array[end];
                    break;
                }
            }
            while (begin < end) {
                if (cmp(pivot, array[begin]) > 0) { //左边元素<轴点元素
                    begin++;
                } else {//左边元素>=轴点元素
                    array[end--] = array[begin];
                    break;
                }
            }
        }

        //将轴点元素放入最终的位置
        array[begin] = pivot;

        //返回轴点元素
        return begin;
    }
}
